package stackqueue;

import java.util.Stack;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/17 16:59
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class Trap {

    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int sum = 0;
        for (int i = 1; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer mid = stack.pop();
                if (!stack.isEmpty()) {
                    int h = Math.min(height[stack.peek()], height[i]) - height[mid];
                    int w = i - 1 - stack.peek();
                    sum += h * w;
                }
            }
            stack.push(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        trap(height);
    }
}
